package com.chapter12;

import com.chapter6.ArrayOperation;
import com.utility.Point;

public class SearchOperation {

	/*
	 * problem 1
	 */
	public int binarySearch(int[] A, int l, int r,int val){
		if(A[l]==val){
			return l;
		}
		if(l>=r)
			return -1;
		
		
		int mid=l+(r-l)/2;
		if(A[mid]>=val){
			return binarySearch(A, l,  mid,val);
		}
		else
			return binarySearch(A, mid+1,  r,val);
	}
	/*
	 * problem 2
	 */
	public int binarySearchGreater(int[] A, int l, int r,int val){
		if(l>=r && val>=A[l])
			return -1;
		if(l==r)
			return l;
		
		if(A[r]==val){
			return r+1;
		}
		
		int mid=l+(r-l)/2;
		if(A[mid]>=val){
			return binarySearchGreater(A, l,  mid,val);
		}
		else
			return binarySearchGreater(A, mid+1,  r,val);
	}
	/*
	 * problem 3
	 */
	public int binarySearchIndex(int[] A, int l, int r){
		if(l>r)
			return -1;
		
		int mid=l+(r-l)/2;
		if(A[mid]==mid)
			return mid;
		if(A[mid]>mid){
			return binarySearchIndex(A, l,  mid-1);
		}
		else
			return binarySearchIndex(A, mid+1,  r);
	}
	
	/*
	 * problem 4
	 */
	public int searchCyclicArray(int [] A,int l, int r){
		if(A[l]<A[r] || l>=r)
			return l;
		if(l==r-1){
			return (A[l]>A[r]?r:l);
		}
			
		int mid=l+(r-l)/2;
		if(A[mid]>=A[l]){
			return searchCyclicArray(A,mid,r);
		}
		else
			return searchCyclicArray(A,l,mid);
	}
	
	public void testCyclic(){
		int[] C={1,2,6,7,8,9,10,11,12,13,14,15,16,17,18,20,24};
		ArrayOperation ao=new ArrayOperation();
		for(int i=0;i<C.length;i++){
			System.out.println("position = "+searchCyclicArray(C, 0, C.length-1)+", length= "+C.length);
			ao.rotate(C, 1);
		}
		
	}
	
	/*
	 * problem 5
	 */
	public int binarySearchRandomLength(int[] A,int k){
		int length=1;
		int l=0;
		int r=0;
		while(true)
		try{
			if(A[length-1]==k){
				return length-1;
			}
			if(A[length-1]>k){
				l=length/2-1;
				r=length-1;
				break;
			}
			length=length*2;
		}
		catch(Exception e){
			l=length/2-1;
			r=length-1;
			break;
		}
		
		while(true){
			try{
				if(l>r)
					return -1;
				int mid=l+(r-l)/2;
				if(A[mid]==k)
					return mid;
				else if(A[mid]>k){
					r=mid-1;
				}
				else
					l=mid+1;
			}
			catch(Exception e){
				r=l+(r-l)/2-1;
			}
		}
	}
	public void testbinarySearchRandomLength(){
		int[] C={1,2,6,7,8,9,10,11,12,13,14,15,16,17,18,20,24};
		int[] B={-1,0,6,7,8,9,10,11,12,13,14,15,16,17,18,20,25};
		for(int i=0;i<C.length;i++){
			System.out.println("position = "+binarySearchRandomLength(C, B[i])+", length= "+C.length);
		}
	}
	/*
	 * problem 7
	 */
	public double getSquareroot(int n){
		double x=n;
		double y=2*n;
		double e=0.001;
		while(y-x>e){
			y=x;
			x=(x+n/x)/2;
		}
		return x;
	}
	
	public int getSquarerootCeil(int n){
		return (int)Math.ceil(getSquareroot(n));
	}
	/*
	 * problem 6
	 */
	public int findSquarerootCeil(int n){
		int root=1;
		int l=1;
		int r=1;
		while(true){
			if(root*root<n)
				root=root*2;
			else if(root*root==n)
				return root;
			else{
				l=root/2;
				r=root;
				break;
			}
		}
		while(true){
			if(l>r)
				return l*l;
			int mid=l+(r-l)/2;
			if(mid*mid==n)
				return n;
			else if(mid*mid>n && (mid-1)*(mid-1)<n)
				return mid*mid;
			else if(mid*mid>n)
				r=mid;
			else
				l=mid;
		}
	}
	/*
	 * problem 9
	 */
	public Point getIndex2darray(int[][] A,int K){
		int i=0;
		int j=A[0].length-1;
		while(i<A.length || j>=0){
			if(j<0 || i>=A.length)
				return new Point(-1,-1,-1);
			
			if(A[i][j]==K){
				return new Point(i,j,-1);
			}
			else if(A[i][j]<K)
				i++;
			else if(A[i][j]>K)
				j--;
			
		}
		return new Point(-1,-1,-1);
	}
	
	public void testgetIndex2darray(){
		int[][] A={
				{1,4,7,9},
				{2,5,8,10},
				{3,6,11,13}
		};
		for(int i=0;i<A.length;i++){
			for(int j=0;j<A[0].length;j++){
				Point p=getIndex2darray(A,12);
				System.out.println("x="+p.getX() +",y="+ p.getY());
			}
		}
	}
	
	public int getNonRepeatingNumber(int[] A){
		int length=32;
		int count=0;
		int num=0;
		for(int j=0;j<length;j++){
			for(int i=0;i<A.length;i++){
				if((A[i]>>j & 1)==1){
					count++;
				}
			}
			if(count%3!=0)
				num=num | (1<<j);
			count=0;
		}
		return num;
	}
	
	public void testgetNonRepeatingNumber(){
		int[] A={1,1,1,2,2,2,4,4,4,6,6,6,1000};
		System.out.println(getNonRepeatingNumber(A));
	}
}
